/*------------------------------------------*/
/* AUTHOR:   Incarnation-p-lee              */
/* DATE:     2013/05/06                     */
/*------------------------------------------*/


void 
bitmap_sort(int *data,size_t len)
{
  register int *iptr;
  int max, min, range = 0;
  unsigned char *map;

  assert(NULL != data);
  getRange(data, len, &max, &min);

  range = (max - min) >> 3;
  map = (unsigned char*)calloc(
    sizeof(unsigned char) , ++range);
 
  iptr = data;
  while(iptr < data + len)
  {
    *(map + ((*iptr - min) >> 3)) |=
      (0x80 >> ((*iptr - min) % 8));
    iptr++;
  }
  
  /*
  print_sorted(map,range,min);
  */
  free(map);
  return;
}

static void
getRange(int *data,size_t len,int *max,int *min)
{
  register int *iptr;
  int dmin,dmax;

  assert(NULL != data);
  iptr = data;
  dmin = *data;
  dmax = *data;
  
  while(iptr < data + len)
  {
    if(*iptr > dmax)
      dmax = *iptr;
    if(*iptr < dmin)
      dmin = *iptr;
    iptr++;
  }

  *min = dmin;
  *max = dmax;

  return;
}

static void
print_sorted(unsigned char *map,int len,int base)
{
  register unsigned char *cptr; 
  unsigned char cbits;
  int segment, offset, value;

  assert(NULL != map);
  cptr = map;
  segment = 0;

  while(cptr < map + len)
  {
    offset = 0;
    cbits = 0x80;
    while(0 != cbits)
    {
      if(cbits == (*cptr & cbits))
      {
        value = base + (segment << 3) + offset;
        fprintf(stdout,"%d,", value);
      }
      cbits >>= 1;
      offset++;
    }
    cptr++;
    segment++;
  }

  fprintf(stdout,"\n");

  return;
}

